package com.lw.leetcode.other.a;

/**
 * Created with IntelliJ IDEA.
 * LCP 22. 黑白方格画
 *
 * @author liw
 * @version 1.0
 * @date 2021/9/30 16:49
 */
public class PaintingPlan {

    public static void main(String[] args) {
        PaintingPlan test = new PaintingPlan();
        // 48
//        int n = 4;
//        int k = 10;
        // 9
//        int n = 3;
//        int k = 8;
        // 0
//        int n = 6;
//        int k = 13;
        // 44
//        int n = 4;
//        int k = 12;
        // 1
        int n = 2;
        int k = 4;
        // 4
//        int n = 2;
//        int k = 2;
        int i = test.paintingPlan(n, k);
        System.out.println(i);
    }


    public int paintingPlan(int n, int k) {
        if (k == 0 || k == n * n) {
            return 1;
        }
        int sum = 0;
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= n; j++) {
                int v = n * (i + j) - i * j;
                if (v > k) {
                    break;
                }
                if (v == k) {
                    int r = i;
                    int t = j;
                    int c = n;
                    int a = 1;
                    int b = 1;
                    while (r > 0) {
                        a *= c--;
                        b *= r--;
                    }
                    c = n;
                    while (t > 0) {
                        a *= c--;
                        b *= t--;
                    }
                    sum += a / b;
                }
            }
        }
        return sum;
    }


}
